package com.sheng.leetcode.year2023.month12.day19;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2023/12/19
 * <p>
 * 1901. 寻找峰值 II<p>
 * <p>
 * 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。<p>
 * 给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。<p>
 * 找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。<p>
 * 你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。<p>
 * 要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法<p>
 * <p>
 * 示例 1:<p>
 * 输入: mat = [[1,4],[3,2]]<p>
 * 输出: [0,1]<p>
 * 解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。<p>
 * <p>
 * 示例 2:<p>
 * 输入: mat = [[10,20,15],[21,30,14],[7,16,32]]<p>
 * 输出: [1,1]<p>
 * 解释: 30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。<p>
 * <p>
 * 提示：<p>
 * m == mat.length<p>
 * n == mat[i].length<p>
 * 1 <= m, n <= 500<p>
 * 1 <= mat[i][j] <= 10^5<p>
 * 任意两个相邻元素均不相等.<p>
 */
public class LeetCode1901 {

    @Test
    public void test01() {
//        int[][] mat = {{1, 4}, {3, 2}};
        int[][] mat = {{10, 20, 15}, {21, 30, 14}, {7, 16, 32}};
        System.out.println(Arrays.toString(new Solution().findPeakGrid(mat)));
    }
}

class Solution {

    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean flag = true;
                // 判断 4 个方向上是否都满足条件
                for (int[] dir : dirs) {
                    int newi = i + dir[0], newj = j + dir[1];
                    if (newi >= 0 && newi < m && newj >= 0 && newj < n) {
                        if (mat[i][j] <= mat[newi][newj]) {
                            // 不满足则结束当前循环
                            flag = false;
                            break;
                        }
                    }
                }
                // 满足条件则返回
                if (flag) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}
